package Day2025_02_28;

public class LeetCode143 {
    public void reorderList(ListNode head) {
        ListNode newHead1 = new ListNode(0);
        newHead1.next = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newHead2 = new ListNode(0);
        newHead2.next = slow;
        ListNode tmp = slow.next;
        slow.next = null;
        while (tmp != null) {
            ListNode nTmp = tmp.next;
            tmp.next = newHead2.next;
            newHead2.next = tmp;
            tmp = nTmp;
        }
        ListNode newHead = new ListNode(0);
        ListNode cur1 = newHead1.next;
        ListNode cur2 = newHead2.next;
        ListNode prev = newHead;
        while (cur1 != slow) {
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;
            if (cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
